#encoding=utf-8

from sys import path
path.append("..\testesJose")

from myutils import encontra_string_em_elemento
from search import Node,FIFOQueue,tree_search

def tree_search(problem, frontier):
    """Sobrescreve a função no módulo search do código em python do livro Inteligência artificial
    com mesmo nome a fim de ter uma saída compatível com o escolhido para o formato de saída do grafo ou árvore
    e a quantidade de nós extendidos durante a procura dependendo se essa função recebe uma fila (FIFOQueue) ou uma pilha
    (Stack) realiza a procura em largura ou a procura em profundidade em uma árvore"""
    """Search through the successors of a problem to find a goal.
    The argument frontier should be an empty queue.
    Don't worry about repeated paths to a state. [Fig. 3.7]"""

    # Lista que tem o formato [[A,[B,C],[D,[E,F]]] onde cada lista interna é um nó e uma lista de
    # nós expandidos
    tree=[]

    # Lista que armazena os nós já visitados (ela será usada para verificar se um nó já existe na
    # árvore para posteriormente dentro da função renomeá-la (exemplo: se já existe A, precisa ser renomeada
    # para A1) a fim de ter uma saída em uma árvore; a biblioteca que mostra graficamente a árvore funciona
    # só para grafos onde os nós não podem repetir
    visitados=[]

    # Esta lista contém os nós que foram expandidos e tem a função de verificar se os nós já existem
    # na árvore para posteriormente dentro da função renomeá-la a fim de ter uma saída em uma árvore
    # a biblioteca que mostra graficamente a árvore funciona só para grafos onde os nós não podem
    # repetir
    fronteira_tree=[]

    # Adiciona na fronteira o nó inicial para a procura e para o grafo
    frontier.append(Node(problem.initial))
    fronteira_tree.append(problem.initial)

    # Armazena a quantidade de nós extendidos
    extendidos=0

    # Aqui começa a procura
    while frontier:
        # Retiramos um nó da fronteira (uma pilha ou fila)
        node = frontier.pop()

        # Repetimos o mesmo processo nas listas para manipular os nós que vão fazer parte do grafo
        noh=fronteira_tree[0]
        del fronteira_tree[0]

        visitados.append(noh)

        # Se é o objetivo
        visitados.append(noh)

        if problem.goal_test(node.state):
            # adiciona o nó ao grafo e uma lista vazia para ele aparecer na janela
            tree.append([node.state,[]])
            return node,tree,extendidos # e retorna o nó com a solução, a árvore que foi construída e o número
            #de nós que foram extendidos

        # O nó é expandido nos subnós e são adicionados à fronteira
        nosASeremAdicionados=node.expand(problem)
        frontier.extend(nosASeremAdicionados)

        # adicionamos mais um nó aos extendidos
        extendidos+=1

        # lista temporária vazia para armazenar os subnós do nó explorado (para a árvore)
        subnohs_temp=[]

        # Neste loop é verificado cada um dos subnós e se ele já estiver na árvore ele é
        # renomeado em uma sequência: se A existe ele é renomeado para A1
        for subnoh in nosASeremAdicionados:
            if (subnoh.state not in fronteira_tree) and (subnoh.state not in visitados):
                subnohs_temp.append(subnoh.state)
                visitados.append(subnoh.state)
                fronteira_tree.append(subnoh.state)
            else:
                pos=encontra_string_em_elemento(sorted(fronteira_tree+visitados),subnoh.state)
                if pos==None or filter(lambda  x:x.isdigit(),(sorted(fronteira_tree+visitados))[pos])=='':
                    ultimo_numero=0
                else:
                    ultimo_numero=int(filter(lambda  x:x.isdigit(),(sorted(fronteira_tree+visitados))[pos]))
                proximo_numero=ultimo_numero+1
                visitados.append(subnoh.state+str(proximo_numero))
                fronteira_tree.append(subnoh.state+str(proximo_numero))
                subnohs_temp.append(subnoh.state+str(proximo_numero))

        # Depois da verificação dos nós adicionamos a lista [nó,[lista_de_subnós]] à árvore
        tree.append([noh,subnohs_temp])

    return None,tree,extendidos # Se não houver solução

def breadth_first_tree_search(problem):
    "Procura em largura em árvore usando uma fila"
    "Search the shallowest nodes in the search tree first."
    return tree_search(problem, FIFOQueue())

def breadth_first_search(problem):
    '''Busca em largura em grafo (sobrescreve a função no módulo search'''
    "[Fig. 3.11]"

    # Lista que armazena o grafo
    graph=[]

    # Número de nós que foram expandidos
    expandidos=0

    # Nó inicial
    node = Node(problem.initial)

    # Testa se é o objetivo e adiciona esse nó e uma lista vazia no grafo para exibição gráfica
    if problem.goal_test(node.state):
        return node,graph,expandidos

    # fronteira
    frontier = FIFOQueue()

    # adiciona o nó à fronteira
    frontier.append(node)

    # a lista de explorados é um conjunto set() porque os nós não podem se repetir em um grafo
    explored = set()

    # Aqui inicia a procura
    while frontier:
        lista=[]   #lista de expandidos

        # É retirado um nó da fronteira
        node = frontier.pop()

        # E adicionado mais um nó nos expandidos

        # É adicionado o nó ao conjunto de explorados (não há repetição de elementos)
        explored.add(node.state)

        # O nó é expandido e se não está na fronteira ou no conjunto de nós explorados
        # é adicionado à fronteira e à lista de nós expandidos
        foi_expandido=False
        for child in node.expand(problem):
            if child.state not in explored and child not in frontier:
                if child.state not in lista:
                    if foi_expandido==False:
                        expandidos+=1
                    foi_expandido=True
                    lista.append(child.state)
                if problem.goal_test(child.state):
                    graph.append([node.state,lista])
                    return child,graph,expandidos
                frontier.append(child)
            else:
                pass

        # A lista de nós expandidos acima é adicionado ao grafo
        graph.append([node.state,lista])


    return None,graph,expandidos
